package demo4;
import java.util.*;
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public class Solution {
    //1.剑指 Offer II 023. 两个链表的第一个重合节点
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode cur1 = headA;
        ListNode cur2 = headB;
        int len1 = 0;
        int len2 = 0;
        while(cur1 != null) {
            len1++;
            cur1 = cur1.next;
        }
        while(cur2 != null) {
            len2++;
            cur2 = cur2.next;
        }
        cur1 = headA;
        cur2 = headB;
        if(len1 > len2) {
            int ans = len1 - len2;
            for(int i = 0; i < ans; i++) {
                cur1 = cur1.next;
            }
            while(cur1 != cur2) {
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
        }else {
            int ans = len2 - len1;
            for(int i = 0; i < ans; i++) {
                cur2 = cur2.next;
            }
            while(cur1 != cur2) {
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
        }
        return cur1;
    }
    //2.剑指 Offer II 026. 重排链表(寻找中间结点 + 反转链表 + 合并链表)
    public void reorderList(ListNode head) {
        //先走一半
        ListNode cur = head;
        ListNode midNode = finMidNode(cur);
        //反转链表
        ListNode tmp2 = midNode.next;
        midNode.next = null;
        ListNode head2 = reverseList(tmp2);
        //合并链表
        mergeList(head, head2);
    }
    private void mergeList(ListNode head1,ListNode head2) {
        while(head1 != null && head2 != null) {
            ListNode tmp1 = head1.next;
            ListNode tmp2 = head2.next;
            head1.next = head2;
            head2.next = tmp1;
            head1 = tmp1;
            head2 = tmp2;
        }
    }
    private ListNode reverseList(ListNode cur) {
        ListNode prev = null;
        while(cur != null) {
            ListNode curNext = cur.next;
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }
        return prev;
    }
    private ListNode finMidNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
    //3.链表组件
    public int numComponents(ListNode head, int[] nums) {
        //哈希法
        Set<Integer> set = new HashSet<>();
        for(int i = 0; i < nums.length; i++) {
            set.add(nums[i]);
        }
        int ret = 0;
        int sum = 0;//每次累计的的最大次数
        ListNode cur = head;
        while(cur != null) {
            if(set.contains(cur.val)) {
                sum++;
            }else{
                if(sum != 0) {
                    ret++;
                }
                sum = 0;
            }
            cur = cur.next;
        }
        if(sum != 0) {
            ret++;
        }
        return ret;
    }
    //4.面试题 02.04. 分割链表
    public ListNode partition(ListNode head, int x) {
        ListNode smallHead = new ListNode(0);
        ListNode small = smallHead;
        ListNode largeHead = new ListNode(0);
        ListNode large = largeHead;
        while(head != null) {
            if(head.val < x) {
                small.next = head;
                small = small.next;
            }else {
                large.next = head;
                large = large.next;
            }
            head = head.next;
        }
        large.next = null;
        small.next = largeHead.next;
        return smallHead.next;
    }

    //6.链表中的下一个更大节点(暴力)
    public int[] nextLargerNodes(ListNode head) {
        //暴力
        ListNode cur = head;
        int len = 0;
        while(cur != null) {
            len++;
            cur = cur.next;
        }
        int[] ret = new int[len];
        cur = head;
        for(int i = 0; i < len - 1; i++) {
            ListNode curCur = cur.next;
            int j = i;
            for(; j < len - 1; j++) {
                if(cur.val < curCur.val) {
                    break;
                }
                curCur = curCur.next;
            }
            if(j == len - 1) {
                ret[i] = 0;
            }else{
                ret[i] = curCur.val;
            }

            cur = cur.next;
        }
        return ret;
    }

    //7.剑指 Offer II 027. 回文链表
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null) {
            return true;
        }
        //先到中间位置
        ListNode fast = head;
        ListNode slow = head;
        while(fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        //反转链表
        ListNode prev = null;
        ListNode cur = slow.next;
        slow.next = null;
        while(cur != null) {
            ListNode curNext = cur.next;
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }
        //检查是否回文
        while(head != null && prev != null) {
            if(head.val != prev.val) {
                return false;
            }
            head = head.next;
            prev = prev.next;
        }
        return true;
    }
    //8.剑指 Offer II 021. 删除链表的倒数第 n 个结点(快慢指针)
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //快慢指针先找到要删除的结点
        ListNode fast = head;
        ListNode slow = head;
        ListNode headNode = new ListNode();//虚拟头结点
        headNode.next = head;
        ListNode prev = headNode;
        for(int i = 0; i < n; i++) {
            fast = fast.next;
        }
        while(fast != null) {
            fast = fast.next;
            prev = slow;
            slow = slow.next;
        }
        //删除
        prev.next = slow.next;
        return headNode.next;
    }
    //9.面试题 02.08. 环路检测
    public ListNode detectCycle(ListNode head) {
        //快指针必须是慢指针速度的二倍
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            //相遇挑出循环
            if(fast == slow){
                break;
            }
        }
        //排除没有环的情况
        if(fast == null || fast.next == null){
            return null;
        }
        //相遇点和头节点同速前进必然会在入口处相遇
        slow = head;
        while(slow != fast){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
    //10.合并两个链表
    public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
        ListNode start = list1;
        ListNode end = list1;
        //start走a - 1步，到删除结点的前面
        for(int i = 0; i < a - 1; i++) {
            start = start.next;
        }
        //end走到b + 1步，到删除结点的后面
        for(int i = 0; i < b + 1; i++) {
            end = end.next;
        }
        ListNode tail = list2;//list2的尾指针
        while(tail.next != null) {
            tail = tail.next;
        }
        //连接
        start.next = list2;
        tail.next = end;
        return list1;
    }
}
//5.链表随机节点(蓄水池法)
class Pool {
    //蓄水池算法
    private ListNode head = null;
    Random random;
    public Pool(ListNode head) {
        this.head = head;
        this.random = new Random();
    }

    public int getRandom() {
        int count = 1;//表示第几个结点(随机值等于count是随机的，因此得到的结点值也是随机的)
        ListNode cur = head;
        int ret = 0;
        while(cur != null) {
            int randomNum = random.nextInt(count) + 1;//生成随机数是[0, count);
            if(count == randomNum) {
                ret = cur.val;
            }
            count++;
            cur = cur.next;
        }
        return ret;
    }
}
